Problem statement: zenit16ckf

Enigma v2.0

Počet bodov: 35, časový limit: 1000ms

Kým ešte Kamila študovala na matfyze, Šandyna si s ňou často šepkala kadejaké interné vtipy a tajomstvá. Odkedy však Kamila odišla do Švajčiarska, musia si písať na diaľku.

Obe by boli rady, ak by ani túto komunikáciu nevedel nik prečítať. A keďže Kamila neverí súčasným šifrovacím schémam, počas prokrastinácie nad bakalárkou vynašla vlastné šifrovacie zariadenie.

Toto zariadenie je principiálne podobné neslávne známej Enigme – má rad otáčacích rotorov, ktorými sa konfiguruje. Každý z rotorov má desať pootočení, ktoré sa po krokoch dajú cyklicky meniť.

Šandyna aj Kamila majú okrem tohto zariadenia identické notesy, kde majú poznačené platné konfigurácie na každý deň. Konfigurácia popisuje, ako majú byť všetky rotory pootočené na to, aby mohli obe strany komunikovať.

Ako si iste viete predstaviť, manuálne pretáčať množstvo rotorov zo včerajšej konfigurácie na dnešnú je strašne únavné. Šandyna by chcela vedieť, ako veľmi sa musí narobiť – teda koľko najmenej krokov treba na zmenu jednej konfigurácie na druhú.

Úloha

Konfigurácia rotorov je popísaná reťazcom \(S\) kde \(i\)-ty znak je pootočenie \(i\)-teho rotora označené cifrou od \(0\) po \(9\). Pootočenie sa dá meniť posunom o \(1\) do ktorejkoľvek strany – teda napríklad pootočenie \(9\) sa dá zmeniť na \(8\) alebo \(0\).

Celý rad rotorov sa pri úprave konfigurácie správa ako jedno prirodzené číslo – pokiaľ \(i+1\)-vý rotor má pootočenie \(9\) a pripočítame k nemu jedna, \(i\)-ty rotor ku svojmu pootočeniu automaticky pripočíta jedna (čo sa zase môže prejaviť pootočením \(i-1\) rotora a kaskádovito ďalej). Podobne fungujú záporné pootočenia.

Jediný problém nastáva, pokiaľ máme príliš krátke zariadenie a pootočením by sa chcel otočiť neexistujúci rotor. V takom prípade sa zariadenie pokazí. Našťastie, vieme na ľavý koniec radu rotorov zadarmo pridávať ľubovoľne veľa rotorov s pootočením \(0\).

Ako krok zmeny konfigurácie definujeme manuálne pootočenie rotora o \(1\).

Dve konfigurácie považujeme za rovnaké, ak sú čísla, ktoré reprezentujú, rovnaké (napr. konfigurácie \(0047\) a \(47\) sú rovnaké).

Vstup a výstup

Na prvom riadku vstupu dostanete včerajšiu konfiguráciu \(V\), na druhom dnešnú konfiguráciu \(D\). Obe konfigurácie budú mať rovnaký počet cifier. Tento počet neprekročí \(1\,000\,000\).

Na výstupe uveďte jedno číslo - najmenší počet krokov potrebných na zmenu konfigurácie \(V\) na \(D\).

Vstup je pomerne veľký, odporúčame použiť rýchlejšie jazyky.

Príklad

Input:

517
437

Output:

3

Stredný rotor sme dvakrát pootočili o +1 a najľavejší raz o -1

Input:

19
24

Output:

5

Pravý rotor päťkrát pootočíme o +1, čím zadarmo získame správnu pozíciu ľavého rotora